package leetcode_500;

import java.util.Stack;

/**
 *@author 周杨
 *Pattern132_456_ 判断string中是否有132形式的子串
 *describe:用栈 AC 78% 
 *see:https://blog.csdn.net/iyangdi/article/details/77366143
 *2018年8月24日 下午9:00:12
 */
public class Pattern132_456_ {
	public static void main(String[] args) {
		Pattern132_456_ test=new Pattern132_456_();
		System.out.println(test.find132pattern1(new int[] {3,5,0,3,4}));
	}
	/**
	 * describe:完美解 用栈 栈中只保留递增元素 同时保留Kmin作为3号位指针  
	 * 每次比较num[i]与kmin的大小 如果比其小 立即return true 因为kmin是出栈元素 说明栈内的比它大
	 * 如果比其大 那么情况栈内比它小的元素 并把弹出的用kmin记录
	 * 此方法相当于保留i-j中最大范围的区间 同时栈底也保留了候选区间
	 * 2018年8月24日 下午8:55:07
	 */
	public boolean find132pattern(int[] nums) {
	    
        if(nums == null) return false;
        int n = nums.length;
        if(n<3) return false;
        
        Stack<Integer> s = new Stack<Integer>();
        int knum = Integer.MIN_VALUE;
        for(int i=n-1; i>=0; i--){
            if(nums[i]<knum) return true;
            while(!s.isEmpty() && nums[i]>s.peek()){
                knum = s.pop();
            }
            s.add(nums[i]);
        }
        return false;
    }

	/**
	 * describe:动态规划 dp每次保存左边比它小的最小的坐标  但是最大的没有保存 3 5 0 3 4用例不AC
	 * 2018年8月24日 下午8:35:24
	 */
	public boolean find132pattern1(int[] nums) {
		if(nums.length==0)
			return false;
        int dp[]=new int[nums.length];
        dp[0]=-1;
        for(int i=1;i<nums.length;++i) {
        	if(nums[i]>nums[i-1])
        		dp[i]=dp[i-1]==-1?i-1:dp[i-1];
        	else if(nums[i]<nums[i-1]) {
        		if(dp[i-1]==-1) {
        			dp[i]=-1;
        			continue;
        		}
        		if(nums[i]>nums[dp[i-1]])
        			return true;
        		else {
        			int index=dp[i-1];//寻找比其小的Index
        			while(index>=0) {
        				if(dp[index]==-1) {
        					dp[i]=-1;
        					break;
        				}
        				if(nums[dp[index]]<nums[i]) {
        					dp[i]=dp[index]==-1?index:dp[index];
        					break;//找到了
        				}
        				else {
        					index=dp[index];
        				}
        			}
        		}
        	}
        }
        return false;
    }
}
